#include <stdio.h>
#include <cstdlib>

typedef struct DNode
{
    int data;
    struct DNode *prior, *next;
} DNode, *DLinkList;

// 初始化双链表（不带头结点）
bool InitList(DLinkList &L)
{
    L = NULL; // 头指针置空
    return true;
}

// 销毁双链表
void DestroyList(DLinkList &L)
{
    DNode *p = L;
    while (p != NULL)
    {
        DNode *temp = p;
        p = p->next;
        free(temp);
    }
    L = NULL;
}

// 在位置i插入元素e
bool ListInsert(DLinkList &L, int i, int e)
{
    if (i < 1)
        return false; // 非法位置

    // 处理在第一个位置插入
    if (i == 1)
    {
        DNode *s = (DNode *)malloc(sizeof(DNode));
        if (s == NULL)
            return false;

        s->data = e;
        s->prior = NULL;
        s->next = L;

        if (L != NULL)
        {
            L->prior = s;
        }

        L = s; // 更新头指针
        return true;
    }

    DNode *p = L; // 指向第一个结点
    int j = 1;    // 当前遍历位置

    // 寻找第i-1个结点
    while (p != NULL && j < i - 1)
    {
        p = p->next;
        j++;
    }

    if (p == NULL)
        return false; // i值不合法

    DNode *s = (DNode *)malloc(sizeof(DNode));
    if (s == NULL)
        return false;

    s->data = e;
    s->next = p->next;
    s->prior = p;

    if (p->next != NULL)
    {
        p->next->prior = s; // 原后继的前驱指向新结点
    }
    p->next = s; // p的后继指向新结点
    return true;
}

// 删除位置i的元素，通过e返回
bool ListDelete(DLinkList &L, int i, int &e)
{
    if (i < 1 || L == NULL)
        return false; // 非法位置或空表

    // 处理删除第一个结点
    if (i == 1)
    {
        DNode *q = L;
        e = q->data;
        L = L->next; // 更新头指针

        if (L != NULL)
        {
            L->prior = NULL; // 新头结点的前驱置空
        }

        free(q);
        return true;
    }

    DNode *p = L; // 指向第一个结点
    int j = 1;    // 当前遍历位置

    // 寻找第i个结点
    while (p != NULL && j < i)
    {
        p = p->next;
        j++;
    }

    if (p == NULL)
        return false; // i值不合法

    e = p->data;
    p->prior->next = p->next; // 前驱结点指向后继

    if (p->next != NULL)
    {
        p->next->prior = p->prior; // 后继结点指向前驱
    }

    free(p);
    return true;
}

// 按值查找元素位置
int LocateElem(DLinkList L, int e)
{
    DNode *p = L; // 指向第一个结点
    int pos = 1;  // 当前位置

    while (p != NULL)
    {
        if (p->data == e)
        {
            return pos; // 找到返回位置
        }
        p = p->next;
        pos++;
    }
    return 0; // 未找到
}

// 按位查找元素值
int GetElem(DLinkList L, int i)
{
    if (i < 1)
        return -1; // 非法位置

    DNode *p = L; // 指向第一个结点
    int j = 1;    // 当前遍历位置

    while (p != NULL && j < i)
    {
        p = p->next;
        j++;
    }

    return (p != NULL) ? p->data : -1;
}

// 打印双链表内容
void PrintList(DLinkList L)
{
    DNode *p = L;
    printf("Forward: [");
    while (p != NULL)
    {
        printf("%d", p->data);
        if (p->next != NULL)
            printf("->");
        p = p->next;
    }
    printf("]\n");
}

// 反向打印双链表内容（验证前驱指针）
void ReversePrint(DLinkList L)
{
    if (L == NULL)
        return; // 空表

    // 移动到最后一个结点
    DNode *p = L;
    while (p->next != NULL)
    {
        p = p->next;
    }

    printf("Backward: [");
    while (p != NULL)
    {
        printf("%d", p->data);
        if (p->prior != NULL)
            printf("<-");
        p = p->prior;
    }
    printf("]\n");
}

// 判空
bool Empty(DLinkList L)
{
    return (L == NULL);
}

int main()
{
    DLinkList L;
    InitList(L); // 初始化

    // 插入元素
    ListInsert(L, 1, 10);
    ListInsert(L, 2, 20);
    ListInsert(L, 3, 30);

    PrintList(L);    // Forward: [10->20->30]
    ReversePrint(L); // Backward: [30<-20<-10]

    // 删除元素
    int deleted;
    ListDelete(L, 2, deleted);
    printf("Deleted: %d\n", deleted); // Deleted: 20

    // 按值查找
    int pos = LocateElem(L, 30);
    printf("Position: %d\n", pos); // Position: 2

    // 按位查找
    int val = GetElem(L, 1);
    printf("Value: %d\n", val); // Value: 10

    DestroyList(L); // 销毁链表
    return 0;
}